package history.tencent1.problem2;

import java.util.*;

/**
 * 这一题可以用树的广度优先来做, 每一个节点值的三种操作, 对应了三种分支, 广度优先第一个达到0的节点深度即为操作次数
 * 不需要树这么个类, 只需要递归操作, 用deque把节点值poll进去
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int caseCount = sc.nextInt();
        while(caseCount -- > 0){
            int target = sc.nextInt();
            System.out.println(getOperationNum(target) );
        }
    }
    public static int getOperationNum(int target){
        Deque<Integer> deque = new LinkedList<>();
        deque.add(target);
        HashSet<Integer> visited = new HashSet<>();
        int minTimes = 0;
        while(!deque.isEmpty()){
            int qSize = deque.size();
            for(int i = 0; i < qSize; i++){
                int x = deque.poll();
                if(x == 0){
                    return minTimes;
                }else{
                    if(!visited.contains(x - 1)){
                        visited.add(x - 1);
                        deque.offer(x - 1);
                    }
                    if(!visited.contains(x/2)&&(x%2 == 0)){
                        visited.add(x/2);
                        deque.offer(x/2);
                    }
                    if(!visited.contains(x/3)&&(x%3 == 0)){
                        visited.add(x/3);
                        deque.offer(x/3);
                    }
                }
            }
            minTimes++;
        }
        return minTimes;
//        System.out.println(target);
//        if(target == 0) return 0;
//        if(target <= 3){
//            if(target == 1) return 1;
//            return 2;
//        }
//        if(target % 3 == 0){
//            return 1 + getOperationNum(target / 3);
//        }
//        if(target % 2 == 0){
//            return 1 + getOperationNum(target / 2);
//        }
//        return 1 + getOperationNum(target - 1);
    }
}
